package String;//输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
//
// 
//
// 示例 1: 
//
// 输入: [10,2]
//输出: "102" 
//
// 示例 2: 
//
// 输入: [3,30,34,5,9]
//输出: "3033459" 
//
// 
//
// 提示: 
//
// 
// 0 < nums.length <= 100 
// 
//
// 说明: 
//
// 
// 输出结果可能非常大，所以你需要返回一个字符串而不是整数 
// 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 
// 
// Related Topics 贪心 字符串 排序 👍 442 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class minNumber {
    public String minNumber(int[] nums) {
        /**
         将数字转换成字符串，存到数组中，然后利用快排，进行排序，排序规则是按照两个字符拼接的大小
         */
        int len = nums.length;
        if(len==0){
            return "";
        }
        String[] strs = new String[len];
        for(int i= 0;i<len;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, len-1);
        StringBuilder sb = new StringBuilder();
        for(String s : strs){
            sb.append(s);
        }
        return sb.toString();


    }

    private void quickSort(String[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        String pivot = arr[left]; // 中间值
        int i = left;
        int j = right;
        while (i < j) {
            //从后面和前边进行组合 compareTo(a1,a2)返回为正数表示a1>a2, 返回为负数表示a1<a2, 返回为0表示a1==a2。
            while (i < j && (arr[j] + pivot).compareTo(pivot + arr[j]) >= 0) {
                j--;
            }
            if(i<j){
                arr[i++] = arr[j];
            }
            while (i < j && (arr[i] + pivot).compareTo(pivot + arr[i]) < 0) {
                i++;
            }
            if(i<j){
                arr[j--] = arr[i];
            }

        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);

    }
}
//leetcode submit region end(Prohibit modification and deletion)
